package com.company;

/**
 * @author zhf
 * @date 2021/12/23
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。
 */
public class BuildTreeBy {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode();
        int[] preorder = {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};
        BuildTreeBy buildTreeBy = new BuildTreeBy();
        treeNode = buildTreeBy.buildTree(preorder,inorder);
        List<Integer> ans = new ArrayList<>();
        List<Integer> list = buildTreeBy.inorderTraversal(treeNode,ans);
        System.out.println(list);

    }

    public List<Integer> inorderTraversal(TreeNode root, List<Integer> list) {
        if (root == null){
            return null;
        }
        inorderTraversal(root.left,list);
        list.add(root.val);
        inorderTraversal(root.right,list);
        return list;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return findTree(preorder,inorder,0, preorder.length - 1, 0, inorder.length - 1);
    }

    /**
     *
     * @param preorder  先序遍历
     * @param inorder   中序遍历
     * @param preLeft  先序遍历左指针
     * @param preRight  先序遍历右指针
     * @param inLeft    中序遍历左指针
     * @param inRight    中序遍历右指针
     * @return
     */
    public TreeNode findTree(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft,int inRight){
        //记录中序遍历中根节点的下标
        int t = 0;
        //先序遍历第一个元素为二叉树的根节点；
        TreeNode root = new TreeNode(preorder[preLeft]);
        //查找中序遍历中的根节点
        for (t = inLeft; inorder[t]!=preorder[preLeft]&&t <= inRight; t++) ;
        //左右子数的长度
        int leftLen = t - inLeft;
        int rightLen = inRight - t;
        //递归左子树
        if (leftLen > 0) {
            root.left = findTree(preorder, inorder, preLeft + 1, preLeft + leftLen, inLeft, t - 1);
        }
        //递归右子树
        if (rightLen > 0) {
            root.right = findTree(preorder, inorder, preRight - rightLen + 1, preRight, t + 1, inRight);
        }
        return root;
    }
}
